package com.heima.leetcode.practice;

/**
 * leetcode 5. 最长回文子串
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/18 21:05
 */
public class E5 {

    /**
     * <h3>方法一：中心向两边扩展</h3>
     * @param s 字符串
     * @return 最长回文子串
     */
    public String longestPalindrome1(String s) {
        char[] charArray = s.toCharArray();
        int startIndex = 0;
        int maxLength = 1;
        for (int i = 0; i < charArray.length; i++) {
            int lengthOdd = extend1(charArray, i, true);
            int lengthEven = extend1(charArray, i, false);
            if (lengthOdd > lengthEven) {
                if (lengthOdd > maxLength) {
                    maxLength = lengthOdd;
                    startIndex = i - ((lengthOdd - 1) >> 1);
                }
            }else {
                if (lengthEven > maxLength) {
                    maxLength = lengthEven;
                    startIndex = i - ((lengthEven - 2) >> 1);
                }
            }
        }
        return s.substring(startIndex, startIndex + maxLength);
    }

    /**
     * 扩展中心向两边检查回文子串
     * @param charArray 字符数组
     * @param i 中心，则选一个作为中心
     * @param selectOne 是否要选一个作为中心
     * @return 回文子串的长度
     */
    private int extend1(char[] charArray, int i, boolean selectOne) {
        int j = selectOne ? i : i + 1;
        while (i >= 0 && j < charArray.length && charArray[i] == charArray[j]){
            i--;
            j++;
        }
        return j  - i - 1; // 注意最后i多减了一次，j多加了一次
    }

    static int startIndex; // 记录最长回文子串的开始位置，包含
    static int endIndex; // 记录最长回文子串的结束位置，包含

    /**
     * <h3>方法二：中心向两边扩展，优化</h3>
     * @param s 字符串
     * @return 最长回文子串
     */
    public String longestPalindrome2(String s) {
        startIndex = 0; // 静态遍历需要初始化，只有一份
        endIndex = 0; // 静态遍历需要初始化，只有一份
        char[] charArray = s.toCharArray();
        for (int i = 0; i < charArray.length; i++) {
            extend2(charArray, i, true);
            extend2(charArray, i, false);
        }
        return new String(charArray, startIndex, endIndex - startIndex + 1);
    }

    /**
     * 扩展中心向两边检查回文子串
     * @param charArray 字符数组
     * @param i 中心，则选一个作为中心
     * @param selectOne 是否要选一个作为中心
     */
    private void extend2(char[] charArray, int i, boolean selectOne) {
        int j = selectOne ? i : i + 1;
        while (i >= 0 && j < charArray.length && charArray[i] == charArray[j]){
            i--;
            j++;
        }
        j--;
        i++;
        // 是否更新最长回文子串
        if (j - i > endIndex - startIndex){
            startIndex = i;
            endIndex = j;
        }
    }

    /*
           s  b  c  c  b  a  b
        s  y  n  n  n  n  n  n
        b     y  n  n  y  n  n
        c        y  y  n  n  n
        c           y  n  n  n
        b              y  n  y
        a                 y  n
        b                    y

        其中dp[i][j]表示i-j索引范围内的字串是否是回文子串
        状态转移方程：
        dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])
        意思就是当前范围的两端和中间都是回文子串
     */
    /**
     * <h3>方法三：动态规划</h3>
     * @param s 字符串
     * @return 最长回文子串
     */
    public String longestPalindrome3(String s) {
        char[] charArray = s.toCharArray();
        boolean[][] dp = new boolean[charArray.length][charArray.length];
        int maxLength = 1;
        int startIndex = 0;
        for (int i = charArray.length - 1; i >= 0; i--){
            for (int j = i; j < charArray.length; j++){
                dp[i][j] = charArray[i] == charArray[j] && (j - i < 3 || dp[i + 1][j - 1]);
                if (dp[i][j] && j - i + 1 > maxLength){
                    maxLength = j - i + 1;
                    startIndex = i;
                }
            }
        }
        return new String(charArray, startIndex, maxLength);
    }
}
